package leetcode

import kotlinetc.createNodeList
import kotlinetc.println
import kotlinetc.toList

//https://leetcode.com/problems/partition-list/

fun main(args: Array<String>) {

   partition(createNodeList("1->4->3->2->5->2"), 3).toList().println()



}

fun partition(head: ListNode?, x: Int): ListNode? {

    if (head?.next == null) return head
    var smallHeader: ListNode? = null

    var bigHeader: ListNode? = null

    var smallP: ListNode? = null

    var bigP: ListNode? = null

    var p = head

    while (p != null) {

        if (p.`val` < x) {

            if (smallHeader == null) {
                smallHeader = p
                smallP = p
            } else {
                smallP?.next = p
                smallP = p
            }
        } else {

            if (bigHeader == null) {
                bigHeader = p
                bigP = p
            } else {
                bigP?.next = p
                bigP = p
            }
        }



        p = p.next

        smallP?.next = null
        bigP?.next = null

    }

    if (smallHeader == null)
        smallHeader = bigHeader
    else smallP?.next = bigHeader

    return smallHeader

}